/*
 *  cda/src/huff.c
 *
 *  (C) 2011 Harry Wei
 */

#include <error.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdint.h>

#include "../include/cda.h"

/*
 * creat_huffman: creat the huffman tree in RAM.
 * @huff: huff man static allocated structure arraies.
 * @frequency: effective characters and their frequencies.
 * @leaf_nodes: effective characters' amounts.
 */

int 
creat_huffman(struct huffman *huff, 
		struct ch_fre *frequency, int leaf_nodes)
{
	int i = 0;
	int get_lchild;
	int get_rchild;
	int nodes = leaf_nodes * 2 - 1;

#define NODE_NUM nodes
	
	for (i = 1; i < leaf_nodes + 1; i++) {
		huff[i].weight = frequency[i].fre;
		huff[i].parent = 0;
		huff[i].lchild = 0;
		huff[i].rchild = 0;
		huff[i].check = 0;
		huff[i].ch = frequency[i].ch;
	}	
	for (i = leaf_nodes + 1; i < NODE_NUM + 1; i++) {
		huff[i].weight = 0;
		huff[i].parent = 0;
		huff[i].lchild = 0;
		huff[i].rchild = 0;
	}

#if !defined(DEBUG)	/* debug */
	for (i = 1; i < NODE_NUM + 1; i++)
		printf("%d %d %d %d\n", huff[i].weight, huff[i].parent,
						huff[i].lchild, huff[i].rchild);
#endif			/* debug over */

	for (i = leaf_nodes + 1; i < NODE_NUM + 1; i++) {
		if (huff_select(huff, i - 1, 
			&get_lchild, &get_rchild)) {
			perror("Select Error!\n");
			return 1;
		}

#if !defined(DEBUG)
		/* debug */
		printf("time %d: %d %d\n", i, get_lchild, get_rchild);
		/* debug over */
#endif

		huff[i].weight = huff[get_lchild].weight 
					+ huff[get_rchild].weight;
		huff[get_lchild].parent = i;
		huff[get_rchild].parent = i;
		huff[i].lchild = get_lchild;
		huff[i].rchild = get_rchild;
	}
	return 0;
}

/*
 * huff_select: pick up two smallest frequencies' characters.
 * @temp: all the nodes' amounts.
 * @get_lchild: one node's number.
 * @get_rchild: the other one's number.
 */

int huff_select(struct huffman *huf, int temp, 
		int *get_lchild, int *get_rchild)
{
	int i = 1;
	struct huffman get_nums[2] = {{0, 0, 0, 0}, 
					{0, 0, 0, 0}};

	for (i = 1; i < temp + 1; i++) {
		if (0 == huf[i].parent) {
			get_nums[0].weight = huf[i].weight;
			break;
		} else {
			continue;
		}
	}
	for (i = 1; i < temp + 1; i++) {
		if (0 == huf[i].parent) {
			if (get_nums[0].weight >= 
				huf[i].weight) {
				get_nums[0].weight = huf[i].weight;
				get_nums[0].lchild = i;
			}
		} else
			continue;
	}
	huf[get_nums[0].lchild].parent = 1;
	for (i = 1; i < temp + 1; i++) {
		if (0 == huf[i].parent) {
			get_nums[1].weight = huf[i].weight;
			break;
		} else {
			continue;
		}
	}
	for (i = 1; i < temp + 1; i++) {
		if (0 == huf[i].parent) {
			if (get_nums[1].weight >= 
					huf[i].weight) {
				get_nums[1].weight = huf[i].weight;
				get_nums[1].lchild = i;
			} else {
				continue;
			}
		}
	}
	*get_lchild = get_nums[1].lchild;
	*get_rchild = get_nums[0].lchild;
	return 0;
}
